package com.cuz.hot100;

import java.util.*;

public class Q39combinedSum {

    public static void main(String[] args) {




        //输入：candidates = [2,3,6,7], target = 7
        //输出：[[2,2,3],[7]]
        class Solution {
            public List<List<Integer>> combinationSum(int[] candidates, int target) {

                Arrays.sort(candidates);
                List<List<Integer>> results = new ArrayList<>();

                if(candidates[0]>target || candidates[candidates.length-1]*candidates.length<target){
                    return results;
                }

                backTrace(results,new LinkedList<Integer>(),0,candidates,target);

                return results;
            }

            private void backTrace(List<List<Integer>> results, LinkedList<Integer>temp,
                                   int index,int[] nums,int target){
                if(target<0){
                    return;
                }
                if(target == 0){
                    results.add(new ArrayList<>(temp));
                }
                if(index == nums.length){
                    return;
                }
                if(nums[index] > target){
                    return;
                }
                if(nums[nums.length-1] * (nums.length-index)<target){
                    return;
                }
                for (int i = index; i<nums.length; i++) {
                    temp.addLast(nums[i]);
                    backTrace(results,temp,i,nums,target - nums[i]);
                    temp.removeLast();
                }
            }
        }
        int[] arr = {7,3};

        System.out.println(new Solution().combinationSum(arr, 17));

        System.out.println(combinationSum1(arr, 7));
    }

    public static List<List<Integer>> combinationSum1(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) {
            return Collections.emptyList();
        }
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        process(candidates, target, 0, 0, res, new LinkedList<Integer>());
        return res;
    }

    private static int process(int[] candidates, int target, int curSum, int index, List<List<Integer>> res, LinkedList<Integer> temp) {
        //当前结果已经太大了 再找下去也没有必要 返回0 表示太大了
        if (curSum > target) {
            return 0;
        }
        if (curSum == target) {
            res.add(new ArrayList<>(temp));
            return 1;
        }
        for (; index < candidates.length; index++) {
            temp.addLast(candidates[index]);
            int preSign = process(candidates, target, curSum + candidates[index], index, res, temp);
            temp.removeLast();
            //如果上一次找到表示太大了 接下来找没有意义 break
            if (preSign == 0) {
                break;
            }
        }
        return 1;
    }
}
